1 \section{10020 - Minimal coverage
}
3 \textbf{Problema:
} dado un conjunto de intervalos $
[L_i,R_i)$, determinar
4 un subconjunto que cubra el segmento $
[0,M)$ y que sea m\'inimo
5 (en el sentido de cardinalidad). En el enunciado los intervalos
6 se notan $
[L,R
]$, pero como los extremos son enteros y hay que
7 cubrir intervalos reales, los problemas son equivalentes.
9 \subsection{Resolución
}
10 Se resolvi\'o mediante una t\'ecnica golosa. La idea del algoritmo
11 es tomar en cada paso alguno de los intervalos cuyo borde izquierdo
12 ya se encuentre cubierto (o a lo sumo coincida con el punto m\'as chico
13 que todav\'ia no est\'e cubierto) y cuyo borde derecho sea lo mayor posible.
17 \caption{Subconjunto de $A$ de cardinal m\'inimo que cubre a $
[0,M)$
}
18 \PARAMS{$A$: conjunto de intervalos $
[L,R)$.
}
19 \ENSURE{ $S$: un conjunto m\'inimo de intervalos de $A$ que cubren $
[0,M)$.
}
20 \STATE $A^
\star :=$ intervalos no vac\'ios de $A$ ordenados crecientemente por $L$.
24 \IF {$A^
\star$ es vac\'ia $
\lor$
\big($A^
\star_0 =
[L,R)$ con $L > final$
\big)
}
25 \STATE\COMMENT{No se puede cubrir el intervalo $
[0,M)$
}
28 \STATE $C := \
{ [L,R)
\gets A^
\star \text{ tales que
} L
\leq final \
}$
29 \STATE\COMMENT{$C$ corresponde a un prefijo no vac\'io de $A^
\star$
}
30 \STATE $I :=
[L_I,R_I)
\in C$ tal que $R_I =
\max\
{R :
[L,R)
\in C\
}$
31 \IF {$R_I
\leq final$
}
32 \STATE\COMMENT{No se puede cubrir el intervalo $
[0,M)$
}
35 \STATE Agregar $I$ a $S$.
36 \STATE $A^
\star := $ sufijo de $A^
\star$ omitiendo los primeros $\#C$ elementos
43 El algoritmo termina porque el conjunto $C$ nunca es vac\'io, y por lo tanto $A^
\star$
45 El invariante del algoritmo es que los intervalos en $S$ cubren el
46 intervalo $
[0,final)$.
47 Al entrar en una iteraci\'on, todav\'ia falta cubrir el intervalo
48 $
[final, M)$. En la rama del
{\bf then
}, no se puede cubrir
49 $
[final, M)$ y por lo tanto tampoco $
[0,M)$.
51 En la rama del
{\bf else
}, el conjunto $C$ no es vac\'io.
52 Corresponde a un prefijo de $A^
\star$ porque los elementos de $A^
\star$
53 est\'an ordenados. Si hay soluci\'on, al menos un intervalo de $C$ debe
54 figurar en ella, porque todos los intervalos restantes de $A^
\star$ no
55 cubren el punto $final$. Se puede encontrar una soluci\'on m\'inima
56 tomando $I$ como alguno de los intervalos de $C$ cuyo extremo
58 Al incluir $I$ en la soluci\'on, todos los dem\'as intervalos
59 de $C$ quedan cubiertos por el contenido de $S$ y por lo tanto
60 se pueden excluir de $A^
\star$.
62 Adem\'as, incluir $I$ en la soluci\'on no puede ser una mala
63 decisi\'on (que ``moleste'' en iteraciones posteriores), porque
64 el hecho de elegir un valor m\'as grande de $R_I$ hace que
65 en iteraciones posteriores el valor de $final$ sea mayor y
66 por lo tanto el conjunto $C$ incluya m\'as intervalos.
68 Para una entrada de $n$ intervalos, la complejidad del algoritmo
69 es $O(n
\log n)$ en peor caso. El paso m\'as costoso es ordenarlos.
70 El resto del algoritmo se reduce a
71 hacer una pasada sobre los intervalos ya ordenados
\footnote{
72 Eventualmente se podr\'ia mejorar la complejidad para que ordenarlos
73 fuera $O(n)$ haciendo bucket sort. El enunciado afirma que el valor
74 de los extremos $L_i, R_i$ es a lo sumo $
50000$. Pueden ser negativos,
75 pero para este problema ser\'ia equivalente considerar los
76 intervalos $
[\max(L_i,
0),
\max(R_i,
0))$.
77 }. Al iterar los intervalos ordenados según su primera componente, no es
78 necesario construir los $C$ de forma expl\'icita. Simplemente se recorre hasta
79 que se obtiene el primer intervalo que cumple que $L_i > final$. El máximo
80 $R_i$ que actualiza a $final$ se puede obtener durante la recorrida. Luego
81 alcanza con seguir iterando desde donde se terminó, ya que los intervalos ya
82 revisados no son candidatos a tener en cuenta. Como la lista de intervalos se
83 recorre a lo sumo una sola vez, el ciclo itera $O(n)$ veces,
84 con lo cual el costo que domina es el de ordenar los intervalos.
86 Las operaciones para manipular intervalos son $O(
1)$ porque
87 los extremos se representan con enteros de
32 bits.
89 En la implementaci\'on del algoritmo en C++ no se incluye el
{\bf if
}
90 cuya condici\'on es $R_I
\leq final$. En ese caso, el
91 algoritmo falla en la siguiente iteraci\'on, porque si
92 $A^
\star$ no es vac\'ia, el primer intervalo no puede ser
93 tal que $L
\leq final$.
95 \subsection{Implementación
}
100 \hlstd{}\hlline{\
1\
}\hldir{\#include\ $<$stdio.h$>$
}\\
101 \hlline{\
2\
}\hlstd{}\hldir{\#include\ $<$iostream$>$
}\\
102 \hlline{\
3\
}\hlstd{}\hldir{\#include\ $<$list$>$
}\\
103 \hlline{\
4\
}\hlstd{}\\
104 \hlline{\
5\
}\hlkwa{using\ namespace\
}\hlstd{std
}\hlsym{;
}\\
105 \hlline{\
6\
}\hlstd{}\\
106 \hlline{\
7\
}\hldir{\#define\ foreachin(it,s)\ for\ (typeof(s.begin())\ it\ =\ (s).begin();\ it\ !=\ (s).end();\ it++)
}\\
107 \hlline{\
8\
}\hlstd{}\\
108 \hlline{\
9\
}\hlkwc{typedef\
}\hlstd{pair
}\hlsym{$<$
}\hlstd{}\hlkwb{int
}\hlstd{}\hlsym{,\
}\hlstd{}\hlkwb{int
}\hlstd{}\hlsym{$>$\
}\hlstd{Intervalo
}\hlsym{;
}\\
109 \hlline{10\
}\hlstd{}\hlkwc{typedef\
}\hlstd{list
}\hlsym{$<$
}\hlstd{Intervalo
}\hlsym{$>$\
}\hlstd{LIntervalo
}\hlsym{;
}\\
110 \hlline{11\
}\hlstd{}\\
111 \hlline{12\
}\hlkwb{bool\
}\hlstd{}\hlkwd{compararPorPrimeraComp
}\hlstd{}\hlsym{(
}\hlstd{}\hlkwb{const\
}\hlstd{Intervalo
}\hlsym{\&\
}\hlstd{p1
}\hlsym{,\
}\hlstd{}\hlkwb{const\
}\hlstd{Intervalo
}\hlsym{\&\
}\hlstd{p2
}\hlsym{)\
{}\\
112 \hlline{13\
}\hlstd{\
}\hlkwa{return\
}\hlstd{p1
}\hlsym{.
}\hlstd{first\
}\hlsym{$<$\
}\hlstd{p2
}\hlsym{.
}\hlstd{first
}\hlsym{;
}\\
113 \hlline{14\
}\hlstd{}\hlsym{\
}}\\
114 \hlline{15\
}\hlstd{}\\
115 \hlline{16\
}\hlkwb{bool\
}\hlstd{}\hlkwd{resolver
}\hlstd{}\hlsym{(
}\hlstd{LIntervalo
}\hlsym{\&\
}\hlstd{intervalos
}\hlsym{,\
}\hlstd{}\hlkwb{int\
}\hlstd{limite
}\hlsym{,\
}\hlstd{LIntervalo
}\hlsym{\&\
}\hlstd{solucion
}\hlsym{)\ \
{}\\
116 \hlline{17\
}\hlstd{\ intervalos
}\hlsym{.
}\hlstd{}\hlkwd{sort
}\hlstd{}\hlsym{(
}\hlstd{compararPorPrimeraComp
}\hlsym{);
}\\
117 \hlline{18\
}\hlstd{\
}\hlkwb{int\
}\hlstd{final\
}\hlsym{=\
}\hlstd{}\hlnum{0}\hlstd{}\hlsym{;\
}\hlstd{}\hlslc{//\ mayor\ coordenada\ cubierta\ hasta\ ahora
}\\
118 \hlline{19\
}\hlstd{\
}\hlkwb{int\
}\hlstd{r
\textunderscore i\
}\hlsym{=\
}\hlstd{}\hlnum{0}\hlstd{}\hlsym{;
}\hlstd{\ \ \
}\hlsym{}\hlstd{}\hlslc{//\ mayor\ coordenada\ hasta\ ahora\ alcanzada
}\\
119 \hlline{20\
}\hlstd{\ Intervalo\ parActual\
}\hlsym{=\
}\hlstd{}\hlkwd{Intervalo
}\hlstd{}\hlsym{(
}\hlstd{}\hlnum{0}\hlstd{}\hlsym{,\
}\hlstd{}\hlnum{0}\hlstd{}\hlsym{);\
}\hlstd{}\hlslc{//\ posible\ candidato\ a\ ser\ agregado
}\\
120 \hlline{21\
}\hlstd{\\
121 \hlline{22\
}\
}\hlkwd{foreachin\
}\hlstd{}\hlsym{(
}\hlstd{it
}\hlsym{,\
}\hlstd{intervalos
}\hlsym{)\ \
{}\\
122 \hlline{23\
}\hlstd{}\hlstd{\ \
}\hlstd{}\hlslc{//\ si\ la\ primera\ componente\ esta\ mayor\ que\ final,\ ya\ miramos
}\\
123 \hlline{24\
}\hlstd{}\hlstd{\ \
}\hlstd{}\hlslc{//\ todo\ el\ C,\ entonces\ hay\ que\ agregar\ el\ intervalo
}\\
124 \hlline{25\
}\hlstd{}\hlstd{\ \
}\hlstd{}\hlkwa{if\
}\hlstd{}\hlsym{(
}\hlstd{it
}\hlsym{{-
}$>$
}\hlstd{first\
}\hlsym{$>$\
}\hlstd{final
}\hlsym{)\ \
{}\\
125 \hlline{26\
}\hlstd{}\hlstd{\ \ \
}\hlstd{solucion
}\hlsym{.
}\hlstd{}\hlkwd{push
\textunderscore back
}\hlstd{}\hlsym{(
}\hlstd{parActual
}\hlsym{);
}\\
126 \hlline{27\
}\hlstd{}\hlstd{\ \ \
}\hlstd{final\
}\hlsym{=\
}\hlstd{r
\textunderscore i
}\hlsym{;\
}\hlstd{}\hlslc{//\ muevo\ el\ borde\ final
}\\
127 \hlline{28\
}\hlstd{}\hlstd{\ \
}\hlstd{}\hlsym{\
}}\\
128 \hlline{29\
}\hlstd{}\hlstd{\ \
}\hlstd{}\hlslc{//\ si\ la\ primera\ componente\ es\ menor\ que\ final\ miro\ si\ el\ intervalo\ sirve
}\\
129 \hlline{30\
}\hlstd{}\hlstd{\ \
}\hlstd{}\hlkwa{if\
}\hlstd{}\hlsym{(
}\hlstd{it
}\hlsym{{-
}$>$
}\hlstd{first\
}\hlsym{$<$=\
}\hlstd{final
}\hlsym{)\ \
{}\\
130 \hlline{31\
}\hlstd{}\hlstd{\ \ \
}\hlstd{}\hlslc{//\ sirve\ si\ llega\ mas\ lejos\ que\ lo\ que\ hay\ hasta\ ahora
}\\
131 \hlline{32\
}\hlstd{}\hlstd{\ \ \
}\hlstd{}\hlkwa{if\
}\hlstd{}\hlsym{(
}\hlstd{it
}\hlsym{{-
}$>$
}\hlstd{second\
}\hlsym{$>$\
}\hlstd{r
\textunderscore i
}\hlsym{)\ \
{}\\
132 \hlline{33\
}\hlstd{}\hlstd{\ \ \ \
}\hlstd{r
\textunderscore i\
}\hlsym{=\
}\hlstd{it
}\hlsym{{-
}$>$
}\hlstd{second
}\hlsym{;
}\\
133 \hlline{34\
}\hlstd{}\hlstd{\ \ \ \
}\hlstd{parActual\
}\hlsym{=\
{*
}}\hlstd{it
}\hlsym{;
}\\
134 \hlline{35\
}\hlstd{}\hlstd{\ \ \ \
}\hlstd{}\hlslc{//\ si\ ademas\ ya\ llegue\ al\ limite,\ termine
}\\
135 \hlline{36\
}\hlstd{}\hlstd{\ \ \ \
}\hlstd{}\hlkwa{if\
}\hlstd{}\hlsym{(
}\hlstd{r
\textunderscore i\
}\hlsym{$>$=\
}\hlstd{limite
}\hlsym{)\ \
{}\\
136 \hlline{37\
}\hlstd{}\hlstd{\ \ \ \ \
}\hlstd{solucion
}\hlsym{.
}\hlstd{}\hlkwd{push
\textunderscore back
}\hlstd{}\hlsym{(
}\hlstd{parActual
}\hlsym{);
}\\
137 \hlline{38\
}\hlstd{}\hlstd{\ \ \ \ \
}\hlstd{}\hlkwa{break
}\hlstd{}\hlsym{;
}\\
138 \hlline{39\
}\hlstd{}\hlstd{\ \ \ \
}\hlstd{}\hlsym{\
}\
}\\
139 \hlline{40\
}\hlstd{}\hlstd{\ \ \
}\hlstd{}\hlsym{\
}}\\
140 \hlline{41\
}\hlstd{}\hlstd{\ \
}\hlstd{}\hlsym{\
}\
}\hlstd{}\hlkwa{else\
}\hlstd{}\hlsym{\
{}\\
141 \hlline{42\
}\hlstd{}\hlstd{\ \ \
}\hlstd{}\hlslc{//\ hay\ un\ hueco\ que\ no\ puedo\ cubrir\ con\ ningun\ intervalo
}\\
142 \hlline{43\
}\hlstd{}\hlstd{\ \ \
}\hlstd{}\hlkwa{break
}\hlstd{}\hlsym{;
}\\
143 \hlline{44\
}\hlstd{}\hlstd{\ \
}\hlstd{}\hlsym{\
}}\\
144 \hlline{45\
}\hlstd{\
}\hlsym{\
}}\\
145 \hlline{46\
}\hlstd{\\
146 \hlline{47\
}\
}\hlkwa{return\
}\hlstd{r
\textunderscore i\
}\hlsym{$>$=\
}\hlstd{limite
}\hlsym{;
}\\
147 \hlline{48\
}\hlstd{}\hlsym{\
}}\\
148 \hlline{49\
}\hlstd{}\\
149 \hlline{50\
}\hlkwb{int\
}\hlstd{}\hlkwd{main
}\hlstd{}\hlsym{(
}\hlstd{}\hlkwb{int\
}\hlstd{argc
}\hlsym{,\
}\hlstd{}\hlkwb{char\
}\hlstd{}\hlsym{{*
}{*
}}\hlstd{argv
}\hlsym{)
}\\
150 \hlline{51\
}\hlstd{}\hlsym{\
{}\\
151 \hlline{52\
}\hlstd{\
}\hlkwb{int\
}\hlstd{casos
}\hlsym{;
}\\
152 \hlline{53\
}\hlstd{\ cin\
}\hlsym{$>$$>$\
}\hlstd{casos
}\hlsym{;
}\\
153 \hlline{54\
}\hlstd{\
}\hlkwa{while\
}\hlstd{}\hlsym{(
}\hlstd{casos\
}\hlsym{$>$\
}\hlstd{}\hlnum{0}\hlstd{}\hlsym{)\ \
{}\\
154 \hlline{55\
}\hlstd{}\hlstd{\ \
}\hlstd{casos
}\hlsym{{-
}{-
};
}\\
155 \hlline{56\
}\hlstd{}\hlstd{\ \
}\hlstd{}\hlkwb{int\
}\hlstd{limite
}\hlsym{,\
}\hlstd{x
}\hlsym{,\
}\hlstd{y
}\hlsym{;
}\\
156 \hlline{57\
}\hlstd{}\hlstd{\ \
}\hlstd{cin\
}\hlsym{$>$$>$\
}\hlstd{limite
}\hlsym{;
}\\
157 \hlline{58\
}\hlstd{}\hlstd{\ \
}\hlstd{x\
}\hlsym{=\
}\hlstd{}\hlnum{1}\hlstd{}\hlsym{;
}\\
158 \hlline{59\
}\hlstd{}\hlstd{\ \
}\hlstd{y\
}\hlsym{=\
}\hlstd{}\hlnum{1}\hlstd{}\hlsym{;
}\\
159 \hlline{60\
}\hlstd{}\hlstd{\ \
}\hlstd{}\hlslc{//\ cargo\ intervalos
}\\
160 \hlline{61\
}\hlstd{}\hlstd{\ \
}\hlstd{LIntervalo\ intervalos
}\hlsym{;
}\\
161 \hlline{62\
}\hlstd{}\hlstd{\ \
}\hlstd{}\hlkwa{while\
}\hlstd{}\hlsym{(
}\hlstd{y\
}\hlsym{!=\
}\hlstd{}\hlnum{0\
}\hlstd{}\hlsym{\textbar \textbar \
}\hlstd{x\
}\hlsym{!=\
}\hlstd{}\hlnum{0}\hlstd{}\hlsym{)\ \
{}\\
162 \hlline{63\
}\hlstd{}\hlstd{\ \ \
}\hlstd{}\hlkwd{scanf\
}\hlstd{}\hlsym{(
}\hlstd{}\hlstr{"\%d\ \%d"
}\hlstd{}\hlsym{,\ \&
}\hlstd{x
}\hlsym{,\ \&
}\hlstd{y
}\hlsym{);
}\\
163 \hlline{64\
}\hlstd{}\hlstd{\ \ \
}\hlstd{}\hlkwa{if\
}\hlstd{}\hlsym{(
}\hlstd{x\
}\hlsym{!=\
}\hlstd{}\hlnum{0\
}\hlstd{}\hlsym{\textbar \textbar \
}\hlstd{y\
}\hlsym{!=\
}\hlstd{}\hlnum{0}\hlstd{}\hlsym{)\ \
{}\\
164 \hlline{65\
}\hlstd{}\hlstd{\ \ \ \
}\hlstd{}\hlkwa{if\
}\hlstd{}\hlsym{(
}\hlstd{x\
}\hlsym{$<$\
}\hlstd{y
}\hlsym{)\ \
{\
}\hlstd{}\hlslc{//para\ no\ cargar\ intervalos\ inutiles
}\\
165 \hlline{66\
}\hlstd{}\hlstd{\ \ \ \ \
}\hlstd{intervalos
}\hlsym{.
}\hlstd{}\hlkwd{push
\textunderscore front
}\hlstd{}\hlsym{(
}\hlstd{}\hlkwd{Intervalo
}\hlstd{}\hlsym{(
}\hlstd{x
}\hlsym{,
}\hlstd{y
}\hlsym{));
}\\
166 \hlline{67\
}\hlstd{}\hlstd{\ \ \ \
}\hlstd{}\hlsym{\
}}\\
167 \hlline{68\
}\hlstd{}\hlstd{\ \ \
}\hlstd{}\hlsym{\
}}\\
168 \hlline{69\
}\hlstd{}\hlstd{\ \
}\hlstd{}\hlsym{\
}}\\
169 \hlline{70\
}\hlstd{}\hlstd{\ \
}\hlstd{}\hlslc{//\ resuelvo\ instancia
}\\
170 \hlline{71\
}\hlstd{}\hlstd{\ \
}\hlstd{LIntervalo\ solucion
}\hlsym{;
}\\
171 \hlline{72\
}\hlstd{}\hlstd{\ \
}\hlstd{}\hlkwa{if\
}\hlstd{}\hlsym{(
}\hlstd{}\hlkwd{resolver
}\hlstd{}\hlsym{(
}\hlstd{intervalos
}\hlsym{,\
}\hlstd{limite
}\hlsym{,\
}\hlstd{solucion
}\hlsym{))\ \
{}\\
172 \hlline{73\
}\hlstd{}\hlstd{\ \ \
}\hlstd{cout\
}\hlsym{$<$$<$\
}\hlstd{solucion
}\hlsym{.
}\hlstd{}\hlkwd{size
}\hlstd{}\hlsym{()\ $<$$<$\
}\hlstd{endl
}\hlsym{;
}\\
173 \hlline{74\
}\hlstd{}\hlstd{\ \ \
}\hlstd{}\hlkwd{foreachin\
}\hlstd{}\hlsym{(
}\hlstd{it
}\hlsym{,\
}\hlstd{solucion
}\hlsym{)\ \
{}\\
174 \hlline{75\
}\hlstd{}\hlstd{\ \ \ \
}\hlstd{cout\
}\hlsym{$<$$<$\
}\hlstd{it
}\hlsym{{-
}$>$
}\hlstd{first\
}\hlsym{$<$$<$\
}\hlstd{}\hlstr{"\ "
}\hlstd{\
}\hlsym{$<$$<$\
}\hlstd{it
}\hlsym{{-
}$>$
}\hlstd{second\
}\hlsym{$<$$<$\
}\hlstd{endl
}\hlsym{;
}\\
175 \hlline{76\
}\hlstd{}\hlstd{\ \ \
}\hlstd{}\hlsym{\
}}\\
176 \hlline{77\
}\hlstd{}\hlstd{\ \
}\hlstd{}\hlsym{\
}\
}\hlstd{}\hlkwa{else\
}\hlstd{}\hlsym{\
{}\\
177 \hlline{78\
}\hlstd{}\hlstd{\ \ \
}\hlstd{cout\
}\hlsym{$<$$<$\
}\hlstd{}\hlnum{0\
}\hlstd{}\hlsym{$<$$<$\
}\hlstd{endl
}\hlsym{;
}\\
178 \hlline{79\
}\hlstd{}\hlstd{\ \
}\hlstd{}\hlsym{\
}}\\
179 \hlline{80\
}\hlstd{}\hlstd{\ \
}\hlstd{cout\
}\hlsym{$<$$<$\
}\hlstd{endl
}\hlsym{;
}\\
180 \hlline{81\
}\hlstd{\
}\hlsym{\
}}\\
181 \hlline{82\
}\hlstd{}\hlsym{\
}}\\
182 \hlline{83\
}\hlstd{}\\